package zhengqc.graph.algorithm;

import zhengqc.graph.data_structure.Graph;

/* 二分图检测
*  适用于无向图 */
public class BipartitionDetection {
    private Graph graph;
    private boolean[] visited;
    private int[] colors;
    private boolean isBipartite;

    public BipartitionDetection(Graph graph) {
        if (graph.isDirected()) {
            throw new IllegalArgumentException("BipartitionDetection doesn't work in Directed-Graph");
        }
        this.graph = graph;
        this.isBipartite = true;
        this.visited = new boolean[graph.getV()];
        this.colors = new int[graph.getV()];
        for (int i = 0; i < this.colors.length; ++i) {
            this.colors[i] = -1;
        }
        // 若某个联通分量不是二分图, 则整个图便不是二分图
        for (int v = 0; v < graph.getV(); ++v) {
            if (!this.visited[v]) {
                if (!dfs(v, 0)) {
                    this.isBipartite = false;
                    break;
                }
            }
        }
    }
    // 当然, 也可以使用 BFS
    private boolean dfs(int v, int color) {
        this.visited[v] = true;
        this.colors[v] = color;
        for (int w: this.graph.getAdjacency(v)) {
            if (!this.visited[w]) { // w 没有被访问过
                if (!dfs(w, 1-color)) {
                    return false;
                }
            } // w 被访问过, 但 w 与 v 的颜色相同, 则可以判断此图不为二分图
            else if (this.colors[w] == this.colors[v]) {
                return false;
            }
        }
        return true;
    }

    public boolean isBipartite() {
        return this.isBipartite;
    }
}
